# -*- coding: utf-8 -*-
"""
一个类似杨辉三角的结构，每个位置的数字可以随意填写，经过某个数字只能到达下层相邻的两个数字。
假设从第一层开始移动，一直移动到最底层，所经过的所有数字之和，定义为路径的长度。求最短路径长度。
"""
from typing import List

Layer_nums = List[int]


def yh_triangle(nums: List[Layer_nums]) -> int:
    """使用二维数组存储每层（每个决策阶段）的每个节点的最小路径值
    :param nums: 每层数据
    :return: 最小路径和
    """
    len_nums = len(nums)  # 阶段的总数
    assert len_nums > 0, "length of nums must be greater than 0"
    status = [[0] * len_nums for i in range(len_nums)]  # 每个阶段的状态值，状态值为当前阶段的最小值
    status[0][0] = nums[0][0]

    for i in range(1, len_nums):
        # 每层首尾，只有一条路径可以到达
        for j in range(i + 1):
            if j == 0:
                status[i][j] = status[i - 1][j] + nums[i][j]
            elif j == i:
                status[i][j] = status[i - 1][j - 1] + nums[i][j]
            else:
                status[i][j] = min(status[i - 1][j - 1] + nums[i][j], status[i - 1][j] + nums[i][j])

    return min(status[-1])


def yh_triangle_space_optimization(nums: List[Layer_nums]) -> int:
    """使用一维数组存储当前正在处理的层（决策阶段）的每个节点的最小路径值。
    要注意的是，在遍历当前层节点时，必须要从后向前遍历
    :param nums: 每层数据
    :return: 最小路径和
    """
    len_nums = len(nums)  # 阶段的总数
    assert len_nums > 0, "length of nums must be greater than 0"
    status = [0] * len_nums
    status[0] = nums[0][0]

    for i in range(1, len_nums):
        for j in range(i, -1, -1):
            if j == i:
                status[j] = status[j - 1] + nums[i][j]
            elif j == 0:
                status[j] = status[j] + nums[i][j]
            else:
                status[j] = min(status[j - 1] + nums[i][j], status[j] + nums[i][j])

    return min(status)


def yh_triangle_bottom_up(nums: List[Layer_nums]) -> int:
    """使用一维数组存储当前正在处理的层（决策阶段）的每个节点的最小路径值。从下向上遍历每一层。
    :param nums: 每层数据
    :return: 最小路径和
    """
    len_nums = len(nums)  # 阶段的总数
    assert len_nums > 0, "length of nums must be greater than 0"
    status = nums[-1].copy()  # 复制最后一层的数据做为初始数据

    for i in range(len_nums - 1, 0, -1):
        for j in range(i):
            status[j] = min(status[j] + nums[i - 1][j], status[j + 1] + nums[i - 1][j])

    # 注意，因为是自底向上处理，最后处理的层为最顶层，只有一个节点，所以返回status[0]元素。
    return status[0]


if __name__ == "__main__":
    test_nums = [[1], [2, 3], [3, 4, 5], [7, 6, 8, 9]]
    print(yh_triangle(test_nums))
    print(yh_triangle_space_optimization(test_nums))
    print(yh_triangle_bottom_up(test_nums))
